﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

class Sol77
{
    IList<IList<int>> res;
public IList<IList<int>> Combine(int n,int k)
    {
        res = new List<IList<int>>();

        List<int> newList = new List<int>();
        DFS(n,k, 1, newList);

        return res;

    }

 public void DFS2(int numsLen, int need,int startIndex, IList<int> list)//经典递归
    {//递归终止条件
        if (list.Count ==need)
        {
            res.Add(list);
            return;
        }


        
        for (int i = startIndex; i <= numsLen; i++)
        {

            List<int> newList = new List<int>(list);
            newList.Add(i);//加入队列

            DFS(numsLen, need, i + 1, newList);
        }


    }public void DFS(int numsLen, int need,int startIndex, IList<int> list)//经典递归，剪枝优化
    {//递归终止条件
        if (list.Count ==need)
        {
            res.Add(list);
            return;
        }


        
        for (int i = startIndex; i <= numsLen-(need-list.Count)+1; i++)
        {

            List<int> newList = new List<int>(list);
            newList.Add(i);//加入队列

            DFS(numsLen, need, i + 1, newList);
        }


    }

}

class Program77 { 



    static void Main77(string[] args)
    {
        Sol77 s = new Sol77();
        int n = 4, k = 2;
        IList<IList<int>> myres =   s.Combine(n, k);
        for (int i = 0; i < myres.Count; i++)
        {
            for(int j = 0; j < myres[i].Count; j++)
            {

                Console.Write(myres[i][j]+"   ");
            }

            Console.WriteLine();
        }


    }

}

